﻿//【案例开放035】0521上机编程“租房信息查询系统”学习交流
//日期：2021-05-28 15:55浏览：59394回复：542026-05-29 失效
// 1. 题目
//今天学习0521工作级第三题、专业级第一题。题目：
// 请设计一个租房信息查询系统，需要实现如下功能：
// laddRoom(int id, int area, int price, int rooms, int[]
// address)：在系统中增加一套编号为 id，面积为 area，月租金为 price，卧室数量为
// rooms，地址坐标为 address（格式为 [横坐标x, 纵坐标y]）的房源：
//若系统中不存在编号为 id的房源，则添加该房源，返回 true；
//若已存在，则将对应房源信息 更新 为新传入的 area、price、rooms 与
// address，并返回 false； ldeleteRoom(int id)：删除系统中编号为 id 的房源：
//若存在编号为 id 的房源，删除此房源并返回 true；若不存在，返回 false。
// lqueryRoom(int area, int price, int rooms, int[] address, int[][]
// orderBy)：查询系统中符合筛选条件的房源，并按排序要求返回房源编号的序列。其中：
// ?筛选条件：面积大于等于 area，月租金小于等于 price，卧室数为 rooms 的房源；
// ?排序要求：按orderBy中的排序条件依次进行排序；若按orderBy排序结果仍相同（含orderBy为空），则按房源编号升序排列。
// orderBy的元素格式为 [parameter,order]。
// 2parameter取值范围[1,3]， 1（表示 area）、2（表示
// price）、3（表示房源坐标与address的曼哈顿距离）； 2order取值仅为 1 和
// -1，1（表示升序）、-1（表示降序）。 例如 orderBy = [[3,1],[1,-1]]
//表示先按照曼哈顿距离升序排列；若曼哈顿距离相同，再按照面积降序排列；若依然相同，则按编号升序排列。
//示例 1：
//输入：
//["RentingSystem","addRoom","addRoom","queryRoom","deleteRoom"]
//[[],[3,24,200,2,[0,1]],[1,10,400,2,[1,0]],[1,400,2,[1,1],[[3,1],[2,-1]]],[3]]
//输出：[null,true,true,[1,3],true]
//解释：
// RentingSystem obj = RentingSystem();
// obj.addRoom(3,24,200,2,[0,1]); // 在系统中添加编号为 3，面积为 24，月租金为
// 200，卧室数为 2，坐标为 [0,1] 的房源，返回 true
// obj.addRoom(1,10,400,2,[1,0]);
// // 在系统中添加编号为 1，面积为 10，月租金为 400，卧室数为 2，坐标为 [1,0]
// 的房源，返回 true obj.queryRoom(1,400,2,[1,1],[[3,1],[2,-1]]); //
// 查询系统中面积大于等于 1，月租金小于等于 400，卧室数为 2 的房源，
//查询所在地坐标为
//[1,1]，先按照距离升序排序，结果相同，再按照月租金降序排序，编号为 1
//的月租金大于编号为 3 的月租金，所以返回 [1,3] obj.deleteRoom(3); // 删除编号为
// 3 的房源，返回 true 注：输出中的 null 表示此对应函数无输出（其中：C
//的构造函数有返回值，但是也是无需输出） 示例 2： 输入：
//["RentingSystem","deleteRoom","addRoom","addRoom","addRoom","addRoom","addRoom","addRoom","queryRoom","queryRoom"]
//[[],[10],[3,24,200,2,[0,1]],[3,24,500,2,[0,1]],[3,27,500,4,[1,1]],[1,27,500,4,[20,43]],[6,35,227,4,[2,4]],[9,20,3540,4,[4,321]],[25,900,4,[10,1],[[1,1],[2,-1],[3,1]]],[25,900,4,[10,1],[]]]
//输出：[null,false,true,false,false,true,true,true,[3,1,6],[1,3,6]]
//解释：
// RentingSystem obj = RentingSystem();
// obj.deleteRoom(10); // 返回 false
// obj.addRoom(3,24,200,2,[0,1]); // 返回 true
// obj.addRoom(3,24,500,2,[0,1]); // 返回 false
// obj.addRoom(3,27,500,4,[1,1]); // 返回 false
// obj.addRoom(1,27,500,4,[20,43]) // 返回 true
// obj.addRoom(6,35,227,4,[2,4]) // 返回 true
// obj.addRoom(9,20,3540,4,[4,321]) // 返回 true
// obj.queryRoom(25,900,4,[10,1],[[1,1],[2,-1],[3,1]]) // 查询系统中面积大于等于
// 25，月租金小于等于 900，卧室数为 4 的房源，
//先按照面积升序排列，接着按月租金降序排列，最后按曼哈顿距离升序排列。返回
//[3,1,6]。 obj.queryRoom(25,900,4,[10,1],[]) // 查询系统中面积大于等于
// 25，月租金小于等于 900，卧室数为 4
// 的房源，由于orderBy为空，则按房源编号升序排列。返回 [1,3,6]。 注：输出中的
// null 表示此对应函数无输出（其中：C 的构造函数有返回值，但是也是无需输出）
//提示：
// 3 <= addRoom, deleteRoom, queryRoom 累计操作数 <= 1000
// 1 <= id <= 1000
// 1 <= area <= 1000
// 1 <= price <= 10^4
// 1 <= rooms <= 10
// address.length == 2
// 0 <= address[0], address[1] <= 10^4
// 0 <= orderBy.length <= 3, orderBy[i].length == 2
// 1 <= orderBy[i][0] <= 3
// orderBy[i][1] == -1 or 1
//若 i != j 则 orderBy[i][0] != orderBy[j][0]
//曼哈顿距离：地址1(x1, y1) 与 地址2(x2, y2)的曼哈顿距离，计算公式 = |x1 - x2| +
//|y1 - y2|。
// 2. 题目分析
//题目理解：
// 1)本题是增删改查的设计题
// queryRoom(int area, int price, int rooms, int[] address, int[][]
// orderBy)：查询系统中符合筛选条件的房源，并按排序要求返回房源编号的序列。
//有两个要求：筛选、排序。
//排序条件orderBy是一个二维数组，orderBy[i][j]的取值范围如下：
// orderBy[i][0] 取值为[1,3] ：1（表示 area）、2（表示
// price）、3（表示房源坐标与address的曼哈顿距离）
// orderBy[i][1]取值为1或者-1：1（表示升序）、-1（表示降序）
// 2)以第二个示例倒数第二个查询为例，人工分析
// obj.queryRoom(25,900,4,[10,1],[[1,1],[2,-1],[3,1]]) // 查询系统中面积大于等于
// 25，月租金小于等于 900，卧室数为 4 的房源 分析： 9,20,3540,4,[4,321]
// 月租金不满足，跳过9；此时符合筛选条件的有3条记录： 3,27,500,4,[1,1]
// 1,27,500,4,[20,43]
// 6,35,227,4,[2,4])
//计算曼哈顿距离后，用表格形式展现为：
// id
// area
// price
// rooms
// distance
// 1
// 27
// 500
// 4
// 52
// 3
// 27
// 500
// 4
// 9
// 6
// 35
// 227
// 4
// 11
//按照题意，排序条件如下[[1,1],[2,-1],[3,1]]
//?[1,1]表示优先按面积升序排列：1和3面积是相等的，都是27；6的面积35最大，所以6肯定是最后。
//?[2,-1]表示在面积相同情况下，接着按月租金降序排列，1和3都是500，1和3的顺序不变。
//?[3,1]表示如果前面条件还相同，再按曼哈顿距离升序排列，1的距离是 |20-10| +
//|43-1|=52; 3的距离是 |1-10| + |1-1|=9，升序排列的结果是3在1的前面 所以，返回
//[3,1,6]。 3)通过数据库来验证
//如果以数据库来分析，设数据库表名为RentingSystem，则SQL查询命令为：select
// id,area,price,rooms,distance FROM RentingSystem order by area,price
// DESC,distance,id
//如果手上没有可用的数据库系统，我们也可以在EXCEL中通过SQL查询命令来验证下：
// SQL语句：select id,area,price,rooms,distance FROM [Sheet1$] order by
// area,price DESC,distance,id 查询结果为： id area price rooms distance
// 3
// 27
// 500
// 4
// 9
// 1
// 27
// 500
// 4
// 52
// 6
// 35
// 227
// 4
// 11
//可以看到，和人工分析的一致。
//解题思路：
//按筛选和排序的顺序可以分为两种实现方法：先筛选再排序、先排序再筛选，差别不是很大。
//从运行效率来讲，先筛选再排序效率更高。
//排序有两种方法：
// l实现一个cmp函数，只sort一次-->推荐做法
// l反向遍历orderBy数组调用sort四次-->效率比较低，且排序算法必须是稳定排序才行，不推荐
// sort+cmp的分工是：sort是排序算法，cmp是比较器、实现的是元素的两两比较。
//在有两个排序条件情况下：只有排序条件1无法区分两个元素的大小时才需要处理排序条件2。
//需要考虑解决的实现问题：
//?用什么数据结构存储房源信息
//?比较函数cmp的入参实际指向的数据类型（和上一个问题紧密相关）
//?如何将函数queryRoom的排序条件orderBy传递到比较函数cmp中
//?如何处理升序和降序
// 1)用什么数据结构存储房源信息
//由于每套房源信息有一个唯一的id：房源编号，所以很自然想到用
// hash(map/dict)来存储所有房源。 又因为1 <= id <=
// 1000，数据规模不大，所以用数组来存储也很方便。
//对于每套房源信息，可以用一个结构体/类来保存，因为id/area/price/rooms/address都是整数，所以也可以用一个int数组来保存。
// 2)比较函数cmp的入参原型是void*，实际的数据类型是什么（主要是C语言涉及这个问题）
//这里主要又分为两种做法：
// l每套房源信息的指针（int * 或者Room*）
// l房源id或者数组下标
// 3)如何将函数queryRoom的排序条件orderBy传递到比较函数cmp中
//这个和具体语言相关。
// l对于非C语言，通常用lambda表达式传递
// l对于C语言，可以用全局变量传递，或者将排序条件包装到cmp函数的入参中
// 4)如何处理升序和降序
//比较高效的做法是将比较结果乘以orderBy[i][1]，尽量避免分成多个函数对于升序、降序各写一部分代码。
// 3. 员工1-C代码:83行、最大圈复杂度8
// 员工2-C++代码：54行、最大圈复杂度15
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define DEBUG
#ifdef DEBUG
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif

class RentingSystem {
 public:
  RentingSystem() {
    this->roomsystem = vector<tuple<int, int, int, int, int>>(1001);
  }
  bool AddRoom(int id, int area, int price, int rooms,
               const vector<int>& address) {
    if (dict.count(id)) {
      roomsystem[id] = {area, price, rooms, address[0], address[1]};
      return false;
    } else {
      roomsystem[id] = {area, price, rooms, address[0], address[1]};
      dict[id] = 1;
      return true;
    }
  }
  bool DeleteRoom(int id) {
    if (!dict.count(id))
      return false;
    else {
      dict.erase(id);
      return true;
    }
  }
  vector<int> QueryRoom(int area, int price, int rooms,
                        const vector<int>& address,
                        const vector<vector<int>>& orderBy) {
    vector<int> ids;
    for (auto item : dict) {
      int id = item.first;
      auto [ar, pr, ro, x, y] = roomsystem[id];
      if (ar >= area && pr <= price && ro == rooms) {
        ids.push_back(id);
      }
    }
    sort(ids.begin(), ids.end(), [&](int a, int b) {
      auto [ara, pra, roa, xa, ya] = roomsystem[a];
      auto [arb, prb, rob, xb, yb] = roomsystem[b];
      int disa = abs(xa - address[0]) + abs(ya - address[1]);
      int disb = abs(xb - address[0]) + abs(yb - address[1]);
      for (auto item : orderBy) {
        if (item[0] == 1 && ara != arb)
          return item[1] == 1 ? ara < arb : ara > arb;
        if (item[0] == 2 && pra != prb)
          return item[1] == 1 ? pra < prb : pra > prb;
        if (item[0] == 3 && disa != disb)
          return item[1] == 1 ? disa < disb : disa > disb;
      }
      return a < b;
    });
    return ids;
  }

 private:
  vector<tuple<int, int, int, int, int>> roomsystem;
  map<int, int> dict;
};
